#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    int lowerbound(vector<int>& nums, long long target)
    {
        int left = 0, right = nums.size();
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        int n = potions.size();
        vector<int> res;
        for (auto& x : spells)
        {
            long long target = (success + (long long)x - 1) / x;
            long long pos = lowerbound(potions, target);
            res.push_back((long long)n - pos);
        }
        return res;
    }

    int lowerbound(const vector<int>& arr, int x)
    {
        int left = 0, right = arr.size();
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (arr[mid] >= x) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int cnt = 0;
        for (auto& x : arr1) {
            unsigned p = lowerbound(arr2, x);
            bool ok = true;
            if (p < arr2.size()) ok &= (arr2[p] - x > d);
            if (p - 1 >= 0 && p - 1 < arr2.size()) ok &= (x - arr2[p - 1] > d);
            cnt += ok;
        }
        return cnt;
    }

    int lowerbound(vector<int>& nums, int val)
    {
        int left = 0, right = nums.size();
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] >= val) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    int maximumCount(vector<int>& nums) {
        int pos1 = lowerbound(nums, 0);
        int pos2 = lowerbound(nums, 1);
        return max(pos1, (int)nums.size() - pos2);
    }

    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (letters[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return letters[right] > target ? letters[right] : letters[0];
    }

    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size(), diff = 0;
        if (m > n) return false;

        vector<int> hash(26);

        for (int i = 0; i < m; ++i)
        {
            --hash[s1[i] - 'a'];
            ++hash[s2[i] - 'a'];
        }

        for (int h : hash)
            if (h != 0) ++diff;

        if (diff == 0) return true;

        for (int i = m; i < n; ++i)
        {
            int x = s2[i] - 'a', y = s2[i - m] - 'a';
            if (x == y) {
                continue;
            }

            if (hash[x] == 0) {
                ++diff;
            }
            ++hash[x];
            if (hash[x] == 0) {
                --diff;
            }

            if (hash[y] == 0) {
                ++diff;
            }
            --hash[y];
            if (hash[y] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }

        return false;
    }

    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        unordered_map<char, int> hash1;
        for (char c : p) hash1[c]++;

        unordered_map<char, int> hash2;
        for (int left = 0, right = 0; right < s.size(); ++right)
        {
            hash2[s[right]]++;
            while (left<right && right - left + 1>p.size())
            {
                hash2[s[left]]--;
                if (hash2[s[left]] == 0) hash2.erase(s[left]);
                ++left;
            }
            if (hash1 == hash2) ret.push_back(left);
        }
        return ret;
    }

    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> hash1;
        for (char c : s1) hash1[c]++;

        unordered_map<char, int> hash2;
        for (int left = 0, right = 0; right < s2.size(); ++right)
        {
            hash2[s2[right]]++;
            while (left<right && right - left + 1>s1.size())
            {
                hash2[s2[left]]--;
                if (hash2[s2[left]] == 0) hash2.erase(s2[left]);
                ++left;
            }
            if (hash1 == hash2) return true;
        }
        return false;
    }
};
